There is conventionally a technique of simulating an operation such as assembly/disassembly of a machine in virtual three-dimensional space in a computer. This technique uses virtual object collision determination to detect contact between objects (Japanese Patent Laid-Open No. 9-311883).
Another technique changes the sequence of collision determination processing and preferentially processes a set of objects which have caused collision in the past, thereby speeding up the processing (Japanese Patent Publication No. 8-5028).
The collision determination processing determines the presence/absence of collision for each combination of geometric elements. For this reason, the processing time generally increases on the order of n! relative to an increase in the amount of data as a collision determination processing target.
The increase in processing time poses a serious problem particularly when operation simulation is done while interactively manipulating virtual objects by, for example, moving or rotating them. This is because if collision determination processing takes a long time, the objects manipulated by the operator cannot immediately react to the manipulation. Since the behavior of the objects largely differs from the physical world, it is impossible to achieve the purpose of simulating the physical world in itself.
For collision determination, it is sometimes necessary to rasterize, on a memory, data with a structure different from that of data for CG rendering in the virtual world. When the amount of data to be subjected to collision determination increases, the memory utilization considerably increases.
For example, Japanese Patent Publication No. 8-5028 discloses a technique of increasing the speed of collision determination processing by changing the sequence of geometric element combinations. However, the collision determination processing is time-consuming until the sequence change finishes. Additionally, this technique cannot solve the problem of heavy pressure on the memory space because it only changes the processing sequence and cannot reduce the amount of data.